package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/">二叉树的最小深度(Minimum Depth of Binary Tree)</a>
 * <p>给定一个二叉树，找出其最小深度。</p>
 * <p>最小深度是从根节点到最近叶子节点的最短路径上的节点数量。</p>
 * <p>说明：叶子节点是指没有子节点的节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *              3
 *            /   \
 *           9     20
 *                /  \
 *               15   7
 *      输出：2
 *
 * 示例 2：
 *      输入：root = [2,null,3,null,4,null,5,null,6]
 *      输出：5
 * </pre>
 * </p>
 * <p>
 * <b>提示： </b>
 * <ul>
 *     <li>树中节点数的范围在 [0, 10^5] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0104MaximumDepthOfBinaryTree_S 二叉树的最大深度(Maximum Depth of Binary Tree)
 * @see LC0111MinimumDepthOfBinaryTree_S 二叉树的最小深度(Minimum Depth of Binary Tree)
 * @since 2025/2/8 15:18
 */
public class LC0111MinimumDepthOfBinaryTree_S {
    static class Solution {
        public int minDepth(TreeNode root) {
            return minDepthByIterator(root);
            //return minDepthByRecursion(root);
            //return minDepthByRecursion2(root);
        }

        private int minDepthByIterator(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<TreeNodeInfo> helper = new LinkedList<>();
            helper.offer(new TreeNodeInfo(root, 1));
            while (!helper.isEmpty()) {
                TreeNodeInfo currNodeInfo = helper.poll();
                TreeNode currNode = currNodeInfo.node;
                int currNodeDepth = currNodeInfo.depth;
                if (currNode.left == null && currNode.right == null) {
                    return currNodeDepth;
                }
                if (currNode.left != null) {
                    helper.offer(new TreeNodeInfo(currNode.left, currNodeDepth + 1));
                }
                if (currNode.right != null) {
                    helper.offer(new TreeNodeInfo(currNode.right, currNodeDepth + 1));
                }
            }
            return 0;
        }

        private int minDepthByRecursion(TreeNode root) {
            if (root == null) {
                return 0;
            }
            // 左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
            if (root.left == null && root.right == null) {
                return 1;
            }
            // 如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度
            int leftMinDepth = minDepthByRecursion(root.left);
            int rightMinDepth = minDepthByRecursion(root.right);
            if (root.left == null || root.right == null) {
                return leftMinDepth + rightMinDepth + 1;
            }
            // 左右孩子都不为空，返回最小深度+1即可
            return Math.min(leftMinDepth, rightMinDepth) + 1;

            // 可简化成下面的代码
            //if (root == null) {
            //    return 0;
            //}
            //int leftMinDepth = minDepthByRecursion(root.left);
            //int rightMinDepth = minDepthByRecursion(root.right);
            //return root.left == null || root.right == null ? leftMinDepth + rightMinDepth + 1 : Math.min(leftMinDepth, rightMinDepth) + 1;
        }

        private int minDepthByRecursion2(TreeNode root) {
            if (root == null) {
                return 0;
            }
            // 左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
            if (root.left == null && root.right == null) {
                return 1;
            }
            if (root.left == null) {
                return minDepthByRecursion(root.right) + 1;
            } else if (root.right == null) {
                return minDepthByRecursion(root.left) + 1;
            }
            return Math.min(minDepthByRecursion(root.right), minDepthByRecursion(root.left)) + 1;
        }
    }

    private static class TreeNodeInfo {
        TreeNode node;
        int depth;

        public TreeNodeInfo(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.left.left = new TreeNode(3);
        Solution solution = new Solution();
        System.out.println(solution.minDepth(node));
    }
}
